package leetcode_500;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *@author 周杨
 *IncreasingSubsequences_491 输出一个数组里递增的子序列 有重复元素
 *describe:重复元素用set去掉 回溯解决 AC 54%
 *2018年9月4日 下午12:44:54
 */
public class IncreasingSubsequences_491 {
	Set<List<Integer>> res;
	
	public List<List<Integer>> findSubsequences(int[] nums) {
		this.res=new HashSet<List<Integer>>();
		if(nums.length==0)
			return new ArrayList<List<Integer>>();
		for(int i=0;i<nums.length;++i) {
			List<Integer> list=new ArrayList<Integer>();
			list.add(nums[i]);
			help(nums,i,list);
		}
		return new ArrayList<List<Integer>>(this.res) ;
    }
	
	public void help(int nums[],int index,List<Integer> list) {
		if(index==nums.length-1)
			return ;
		int i=1;
		int now=list.get(list.size()-1);//当前递增的最后一个数
		while(index+i<nums.length) {
			if(nums[index+i]>=now) {
				Integer t=new Integer(nums[index+i]);
				list.add(t);
				List<Integer> temp=new ArrayList<Integer>(list);
				this.res.add(temp);
				help(nums,index+i,list);
				list.remove(t);
			}
			++i;
		}
	}
	
}
